package com.yeung.swordoffer;


import java.util.ArrayList;
import java.util.Stack;

/**
 * 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。
 * 假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，
 * 序列4,5,3,2,1是该压栈序列对应的一个弹出序列，
 * 但4,3,5,1,2就不可能是该压栈序列的弹出序列。
 * （注意：这两个序列的长度是相等的）
 */
public class 栈的压入_弹出序列 {

    public static void main(String[] args) {
        int pa[] = {1, 2, 3, 4, 5};
        int pb[] = {4, 5, 3, 2, 1};
        IsPopOrder(pa, pb);
    }


    public static boolean IsPopOrder(int[] pushA, int[] popA) {
        Stack<Integer> stack = new Stack<>();
        ArrayList<Integer> list = new ArrayList<>();//记录出栈的顺序
        int x = 0;//记录当前要比较的出栈的元素下标
        for (int item : pushA) {
            stack.push(item);//依次入栈, 当遇到和要比较的popA中顺序的元素相等时,就出栈,并记录下来出栈的顺序
            if (item == popA[x]) {
                list.add(stack.pop());
                x++;//下标右移动, 如第一次是4, 移动后是5
            }
        }
        //所有元素都已经入栈后(中途有和popA序列顺序匹配出栈的, 已经记录在list中)
        // 把剩下的元素全出栈
        while (!stack.isEmpty()) {
            list.add(stack.pop());
        }
        boolean flag = true;
        //查看顺序是否一致,以判断是否是合法的出栈序列
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
            if (list.get(i) != popA[i]) flag = false;
        }
        return flag;
    }
}
